# -*- coding:utf-8 -*-
"""
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
"""
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        # 判断nums1和nums2的状态，都存在则组装nums3
        if nums1 and nums2:
            num1, num2 = reform1(nums1, nums2)
            nums3 = reform2(num1, num2)
        elif nums1:
            nums3 = nums1
        elif nums2:
            nums3 = nums2
        # 计算中位数
        middle = is_middle(nums3)
        return middle


def reform1(num1, num2):
    """
    找出首元素小的list

    :param num1: 
    :param num2: 
    :return: 
    """
    if num1[0] > num2[0]:
        return (num2, num1)
    else:
        return (num1, num2)


def reform2(num1, num2):
    """
    插入排序

    :param num1: 
    :param num2: 
    :return: 
    """
    num3 = num1
    for i in num2:
        for j in num1:
            if i < j:
                num3.insert(num3.index(j), i)
                break
            elif i < num1[-1]:
                continue
            else:
                num3.append(i)
                break
    return num3


def is_middle(num3):
    """
    计算中位数

    :param num3: 
    :return: 
    """
    m, n = divmod(len(num3), 2)
    if n == 0:
        middle = (num3[m] + num3[m - 1]) / 2.00000
    else:
        middle = num3[m]
    return middle